home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / std / c / 698 < prev    next >
Encoding:
Internet Message Format  |  1996-08-06  |  3.0 KB
  1. Path: inforamp.net!usenet
  2. From: pcurran@inforamp.net (Peter Curran)
  3. Newsgroups: comp.std.c
  4. Subject: Re: Restrictions on qsort compare function?
  5. Date: Fri, 05 Apr 1996 04:51:40 GMT
  6. Organization: PSC Enterprises
  7. Message-ID: <4k28t4$2g0@sam.inforamp.net>
  8. References: <4iokop$h4p@lyra.csx.cam.ac.uk> <4iqjar$2m9@usenet.pa.dec.com> <4jgltp$f9l@lyra.csx.cam.ac.uk> <828644274snz@genesis.demon.co.uk>
  9. Reply-To: pcurran@inforamp.net
  10. NNTP-Posting-Host: ts9-02.tor.istar.ca
  11. X-Newsreader: Forte Free Agent 1.0.82
  12.  
  13. On Thu, 04 Apr 96 18:57:54 GMT in article <828644274snz@genesis.demon.co.uk>
  14.     Lawrence Kirby <fred@genesis.demon.co.uk> (Lawrence Kirby) wrote:
  15.  
  16. >In article <4jgltp$f9l@lyra.csx.cam.ac.uk>
  17. >           jkb@mrc-lmb.cam.ac.uk "James Bonfield" writes:
  18.  
  19. >>I now agree that non antisymmetric or nontransitive sort comparison functions
  20. >>are indeed invalid. I can see how this can be construed from the ansi
  21. >>standard, but can also see how it's possible to construe otherwise.
  22.  
  23. >I don't. 7.10.5.2:
  24.  
  25. >"The contents of the array are sorted into ascending
  26. > order according to a comparison function pointed to by compar". 
  27.  
  28. >If the comparison function produces inconsistent results then it is at odds
  29. >with that sentence. At best that sentence has no well-defined meaning and
  30. >the 'sort' operation as a whole has undefined behaviour.
  31.  
  32. <snip>
  33.  
  34. From the standard:
  35. >"The function shall return an integer less than, equal to, or greater than
  36. > zero if the first argument is considered to be respectively less than, equal
  37. > to, or greater than the second."
  38.  
  39. Again, agreeing that the intent was that the comparison function be consistent,
  40. this statement does not require it.  (Actually, consistent is not quite the word
  41. I mean here - it must be consistent with a well-specified definition  - that is
  42. implied by the first quote, above -  but that definition need not lead to a
  43. comparison function that produces the same result for the same values on
  44. successive calls, or follows other "sensible" patterns.)
  45.  
  46. There is nothing here that demands that what one "considers to be ... less
  47. than", etc., remain static over the duration of a call to qsort().  As I
  48. suggested earlier, one could define a ordering that is time-dependent, or
  49. changes in some other way between calls to the comparison function.  I see
  50. nothing here that precludes a comparison function from then implementing such a
  51. definition.  As long as the comparison function produces results match the rules
  52. that have been established for considering values to be less than, etc., each
  53. other each time it is called, whether those rules are static or not,, the
  54. requirements of the standard have been met.
  55.  
  56. This is clearly "language lawyering" of the worst kind.  Anyone who writes such
  57. a comparison function will almost certainly get a well-earned mess.  However, I
  58. see nothing in the standard that contradicts this interpretation.  For logical
  59. correctness, I think the definition of the comparison function needs to be
  60. tightened, although its hardly of pressing urgency.)
  61.  
  62. --
  63. Peter Curran                               pcurran@inforamp.net
  64.  
  65.